package pers.course.others;

import java.util.Scanner;

public class Extend_GCD {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        System.out.println(eGCD(a, b));
    }

    public static int eGCD(int a, int b) {
        int[] x = {1, 0, a};
        int[] y = {0, 1, b};
        int[] t = new int[3];
        int q = 0;
        boolean flag = true;
        while (flag) {
            q = x[2] / y[2];
            for (int i = 0; i < 3; i++) {
                t[i] = x[i] - q * y[i];
                x[i] = y[i];
                y[i] = t[i];
            }
            if (y[2] == 1) {
                if (y[1] < 0) {
                    y[1] += a;
                }
                return y[1];
            }
            if (y[2] == 0) {
                flag = false;
            }
        }
        return 0;
    }
}
